public class HashTable {
    static class Entry{
        public Entry(int hash,Object key,Object value) {
            this.hash=hash;
            this.key = key;
            this.value=value;
        }
        private  int hash;
        private Object key;
        private Object value;
        private  Entry next;
    }
    Entry[] entries=new Entry[16];
    int size=0;
    float Loadfactory=0.75f;
    public Object get(int hash,Object key){
        int indx=hash & (entries.length-1);
        if(entries[indx]==null){
            return null;
        }
        while (entries[indx]!=null){
            if(entries[indx].key.equals(key)){
                return entries[indx].value;
            }
            entries[indx]=entries[indx].next;
        }
        return null;
    }
    public void put(int hash,Object key,Object value){
        int indx=hash & (entries.length-1);
        if(entries[indx]==null){
            entries[indx]=new Entry(indx,key,value);
        }
        else {
            while (entries[indx]!=null){
                if(entries[indx].key.equals(key)){
                    entries[indx].value=value;
                    return;
                }
                entries[indx]=entries[indx].next;
            }
            entries[indx]=new Entry(indx,key,value);
        }
        if(this.size==(int)(entries.length*Loadfactory)){
            resize();
        }
        this.size++;
    }
    private void resize(){    //扩容
        Entry[] newentrie=new Entry[entries.length*2];
        for (int i = 0; i < entries.length; i++) {
            if(entries[i]!=null){
                Entry a=null;
                Entry b=null;
                Entry aHead=null;
                Entry bHead=null;
                while (entries[i]!=null){
                  if((entries[i].hash & entries.length)==0){
                      if(a==null){
                          aHead=entries[i];
                      }
                      else {
                          a=a.next;
                      }
                      a=entries[i];
                  }
                  else {
                      if(b==null){
                          bHead=entries[i]
                      }
                      else {
                          b=b.next;
                      }
                      b=entries[i];
                  }
                  entries[i]=entries[i].next;
              }
            }
        }
        entries=newentrie;
    }
    public Object remove(int hash,Object key){
        int indx=hash & (entries.length-1);
        if(entries[indx]==null){
            return null;
        }
        else {
            while (entries[indx].next!=null){
                if(entries[indx].next.key.equals(key)){
                    Entry entry=entries[indx];
                    entries[indx].next=entries[indx].next.next;
                    return entry.value;
                }
                entries[indx]=entries[indx].next;
            }
            if(entries[indx].key.equals(key)){
                Entry entry=entries[indx];
                entries[indx]=null;
                return entry.value;
            }
        }
        return null;
    }
}
